import java.util.Arrays;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2025-03-20
 * Time: 13:02
 */

public class BinarySearch {
    /**
     * 1.二分查找
     * 时间复杂度: O(logN)
     * 空间复杂度: O(1)
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + (right - left)/2;
            if(nums[mid] > target) {
                right = mid - 1;
            }else if (nums[mid] < target) {
                left = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 2.在排序数组中查找元素的第一个和最后一个位置
     * 时间复杂度: O(logN)
     * 空间复杂度: O(1)
     * @param nums
     * @param target
     * @return
     */
    public static int[] searchRange(int[] nums, int target) {
        int[] ret = new int[]{-1,-1};

        //空数组处理
        if(nums.length == 0) {
            return ret;
        }
        int left = 0, right = nums.length - 1;

        //查找区间的左端点
        while(left < right) {//不能取等于 会陷入死循环
            int mid = left + (right - left)/2;//不能写成(right - left + 1)会陷入死循环
            if(nums[mid] < target) {
                left = mid + 1;//想要跳出[left,mid]这个区间
            }else {
                right = mid;//不能跳出[mid,right]这个区间
            }
        }

        //不存在处理
        if(nums[left] != target) {
            return new int[]{-1,-1};
        }
        ret[0] = left;

        //查找区间的右端点
        //left = 0;//这里可以不写，可以直接从上面left所在位置接着往后面找
        right = nums.length - 1;
        while(left < right) { //不能取等于 会陷入死循环
            int mid = left + (right - left + 1)/2;//不能写成(right - left)会陷入死循环
            if(nums[mid] <= target) {
                left = mid;//不能跳出[left,mid]这个区间
            }else {
                right = mid - 1;//想要跳出[mid,right]这个区间
            }
        }
        ret[1] = left;
        return ret;
    }

    /**
     * 3.x的平方根
     * 0 <= x <= 2^31 - 1
     * @param x
     * @return
     */
    public static int mySqrt(int x) {
        //细节处理
        if(x < 1) return 0;
        long left = 1, right = x;
        while(left < right) {
            long mid = left + (right - left + 1)/2;
            if(mid * mid <= x) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return (int)left;
    }

    /**
     *4.搜索插入的位置
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length -1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        return nums[left] < target ? left + 1 : left;
    }

    /**
     * 5.山脉数组的顶峰索引
     * @param arr
     * @return
     */
    public static int peakIndexInMountainArray(int[] arr) {
        int left = 1, right = arr.length - 2;
        while(left < right) {
            int mid = left + (right - left + 1)/2;
            if(arr[mid] >= arr[mid-1]) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return left;
    }

    /**
     * 6.寻找峰值
     * @param nums
     * @return
     */
    public static int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] > nums[mid+1]) {
                right = mid;
            }else {
                left = mid + 1;//对于所有有效的 i 都有 nums[i] != nums[i + 1]
            }
        }
        return left;
    }

    /**
     * 7.寻找旋转排序数组中的最小值
     * @param nums
     * @return
     */
    public static int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        int target = nums[right];
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] > target) {
                left = mid +1;
            }else {
                right = mid;
            }
        }
        return nums[left];
    }
    /**

     */
    /**
     * 8.点名 (寻找0~n-1中缺失的数字)
     * 1.哈希表
     * 2.直接遍历找结果
     * 3.位运算(异或)
     * 4.数学（高斯求和公式）
     * 5.二分查找
     */
    /**
     *  5.二分查找
     *  时间复杂度：O(logN)
     * @param records
     * @return
     */
    public static int takeAttendance5(int[] records) {
        int left = 0, right = records.length - 1;
        while(left < right) {
            int mid = left + (right - left)/2;
            if(records[mid] == mid) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        //处理细节
        return records[left] == left ? left + 1 : left;
    }

    /**
     * 1.哈希表
     * 时间复杂度:O(N)
     * 空间复杂度:O(N)
     * @param records
     * @return
     */
    public static int takeAttendance1(int[] records) {
        Set<Integer> hash = new HashSet<>();
        int n = records.length;
        for(int i = 0; i < n; i++) {
            hash.add(records[i]);
        }
        for(int i = 0; i <= n; i++) {
            if(!hash.contains(i)) {
                return i;
            }
        }
        return n;
    }

    /**
     * 2.直接遍历找结果
     * 时间复杂度：O(N)
     * @param records
     * @return
     */
    public int takeAttendance2(int[] records) {
        for(int i = 0; i < records.length; i++) {
            if(i != records[i]) {
                return i;
            }
        }
        return records.length;
    }

    /**
     * 3.异或
     * 时间复杂度：O(N)
     * @param records
     * @return
     */
    public int takeAttendance3(int[] records) {
        int ret = 0;
        for(int i = 0; i < records.length; i++) {
            ret ^= records[i];
            ret ^= i;
        }
        ret ^= records.length;
        return ret;
    }

    /**
     * 4.数学（高斯求和公式）
     * 时间复杂度：O(N)
     * @param records
     * @return
     */
    public static int takeAttendance4(int[] records) {
        int ret = 0;
        for(int i = 0; i <= records.length; i++) {
            ret += i;
            if(i < records.length) {
                ret -= records[i];
            }
        }
        return ret;
    }
    public static void main(String[] args) {
        int[] array = {};
        int[] ret = searchRange(array,6);
        System.out.println(Arrays.toString(ret));
    }
}
